package Salesman;

import Salesman.Data.DataProvider;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class TSPDynamic extends TSPEngine {

    StepDyn gui_step;
    Step stepx;
    int cityCount;
    int first;
    double way;
    StepDyn[][] cache;
    Distances data = DataProvider.getDistances();

    public TSPDynamic() {
        this(DataProvider.getCityData().size());
    }

    public TSPDynamic(int cityCount) {
        this.cityCount = cityCount;
    }

    private StepDyn start(int first) {
        data = DataProvider.getDistances();
        cityCount = DataProvider.getCityData().size();
        cache = new StepDyn[cityCount][1 << (cityCount)];
        this.first = first;
        BitSet bs = new BitSet(cityCount);
        for (int i = 0; i < cityCount; i++) {
            if (DataProvider.getCityData().get(i).isInSimulation()) {
                bs.set(i);
            }
        }
        StepDyn s = new StepDyn(first, 0);
        way = way(s, without(bs, first));
        return s;
    }

    private double way(StepDyn step, BitSet rest) {
        int idx = toInt(rest);
        if (cache[step.getCity()][idx] == null) {
            if (rest.isEmpty()) {
                double m = data.get(step.getCity(), first);
                cache[step.getCity()][idx] = new StepDyn(first, m);
            } else {
                double m = Double.MAX_VALUE;
                int city = 0;
                StepDyn x = null;
                for (int i = rest.nextSetBit(0); i >= 0; i = rest.nextSetBit(i + 1)) {
                    StepDyn y = new StepDyn(i, 0);
                    double d = data.get(step.getCity(), i) + way(y, without(rest, i));
                    if (d < m) {
                        x = y;
                        m = d;
                        city = i;
                    }
                }
                StepDyn s = new StepDyn(city, m);
                s.linkTo(x.next());
                cache[step.getCity()][idx] = s;
            }
        }
        step.linkTo(cache[step.getCity()][idx]);
        return cache[step.getCity()][idx].getWay();
    }

    public double getWay() {
        return way;
    }

    public static int toInt(BitSet bs) {
        int result = 0;
        for (int i = 0; i < bs.size(); i++) {
            if (bs.get(i)) {
                result |= 1 << i;
            }
        }
        return result;
    }

    public static BitSet without(BitSet bs, int i) {
        bs = (BitSet) bs.clone();
        bs.clear(i);
        return bs;
    }

    @Override
    public void start(City city) {
        stepx = new Step();
        gui_step = start(DataProvider.getCityData().indexOf(city));
    }

    @Override
    public boolean next() {
        boolean b = gui_step.hasNext();
        if (b) {
            stepx.getCities().add(DataProvider.getCityData().get(gui_step.getCity()));
            fireListener(stepx);
            gui_step = gui_step.next();
        } else {
            stepx.getCities().add(DataProvider.getCityData().get(first));
            fireListener(stepx);
            gui_step = null;
        }
        return gui_step != null;
    }

    @Override
    public String toString() {
        return "Dynamische Programmierung";
    }

    private class Step extends AbstractStep {

        List<City> cities = new ArrayList<City>();

        public Step() {
        }

        @Override
        public List<City> getCities() {
            return cities;
        }

        @Override
        public String toString() {
            double complete = 0, step = 0;
            for (int i = 0; i < (cities.size() - 1); i++) {
                step = DataProvider.getDistances().get(
                        DataProvider.getCityData().indexOf(cities.get(i)),
                        DataProvider.getCityData().indexOf(cities.get(i + 1)));
                complete += step;
            }
            DecimalFormat f = new DecimalFormat("0.#");

            return "Route: " + routeToString() + "\n"
                    + "Teilweg: " + f.format(step) + " km\n"
                    + "Gesamtweg: " + f.format(complete) + " km\n\n";
        }
    }
}

class StepDyn {

    private int city;
    private double way;
    private StepDyn next;

    public StepDyn(int city, double way) {
        this.city = city;
        this.way = way;
    }

    public int getCity() {
        return city;
    }

    public void setCity(int city) {
        this.city = city;
    }

    public double getWay() {
        return way;
    }

    public void setWay(double way) {
        this.way = way;
    }

    public void linkTo(StepDyn step) {
        next = step;
    }

    public boolean hasNext() {
        return next != null;
    }

    public StepDyn next() {
        return next;
    }
}